package com.dkd.day20250727;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

import static java.util.Arrays.stream;

public class Main43 {
    //书籍的长、宽都是整数对应 (l,w)。如果书A的长宽度都比B长宽大时，则允许将B排列放在A上面。现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个规格书籍能叠放在一起。
    //
    //输入描述
    //输入：books = [[20,16],[15,11],[10,10],[9,10]]
    //
    //说明：总共4本书籍，第一本长度为20宽度为16；第二本书长度为15宽度为11，依次类推，最后一本书长度为9宽度为10.
    //
    //输出描述
    //输出：3
    //
    //说明: 最多3个规格的书籍可以叠放到一起, 从下到上依次为: [20,16],[15,11],[10,10]
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();

        Integer[][] books =
                Arrays.stream(input.substring(1, input.length() - 1).split("(?<=]),(?=\\[)"))
                        .map(
                                s ->
                                        Arrays.stream(s.substring(1, s.length() - 1).split(","))
                                                .map(Integer::parseInt)
                                                .toArray(Integer[]::new))
                        .toArray(Integer[][]::new);


        System.out.println(solve(books));
    }

    public static int solve(Integer[][] books){
        //长度升序，相同，宽带降序，获得宽带数组
        Arrays.sort(books, (a, b) -> a[0] - b[0]==0?b[1]-a[1]:a[0]-b[0]);
        Integer[] widths =Arrays.stream(books).map(book->book[1]).toArray(Integer[]::new);
        return solve2(widths);
    }

    public static int solve2(Integer[] nums){
        //最优子数列
        ArrayList<Integer> dp = new ArrayList<>();
        dp.add(nums[0]);

        for (int i = 1; i < nums.length; i++) {
            //如果nums[i]>最后一个,天骄
            if(nums[i] > dp.get(dp.size()-1)){
                dp.add(nums[i]);
            }

            //如果小于开头，替换
            if(nums[i] < dp.get(0)){
                dp.set(0, nums[i]);
                continue;
            }

            int index = Collections.binarySearch(dp, nums[i]);
            if(index < 0)  dp.set(-index-1, nums[i]);


        }

        return dp.size();

    }
}
